#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    EMPTY_STR_SLOT = ""

    def expressionExpand(self, string):
        # return self.expressionExpand_non_rec(string, 0)

        self.len = len(string)
        decode_str, _ = self.expressionExpand_rec(string, 0)
        return decode_str

    def expressionExpand_rec(self, string, idx):
        # 递归法
        # slot += alpha
        # slot += num * inner
        slot = ""
        num = 0

        while idx < self.len:
            c = string[idx]

            if c.isdigit():
                # 读取digit
                digit_start = idx
                while string[idx].isdigit():
                    idx += 1
                digit_end = idx
                num = int(string[digit_start:digit_end])
                print('num %s' % num)
            elif c == '[':
                print('[')
                # 递归读取"[]"内部
                inner_str, idx = self.expressionExpand_rec(string, idx+1)
                slot += num * inner_str
            elif c == ']':
                print(']')
                return slot, idx+1
            else:
                assert c.isalpha()
                alpha_start = idx
                while idx < self.len and string[idx].isalpha():
                    idx += 1
                alpha_end = idx
                slot += string[alpha_start:alpha_end]
                print('alpha %s' % string[alpha_start:alpha_end])

        # 最后返回: 内部返回都在 c == '['
        return slot, idx

    def expressionExpand_non_rec(self, string):
        # 非递归法: 使用stack
        self.str_stack = []
        self.num_stack = []
        self.len = len(string)
        self.string = string

        self.str_stack.append(self.EMPTY_STR_SLOT)

        idx = 0
        while idx < self.len:
            c = string[idx]

            if c.isdigit():
                idx = self._do_digit(idx)
            elif c.isalpha():
                idx = self._do_alpha(idx)
            else :
                idx = self._do_close_brace(idx)

        return self.str_stack.pop()

    def _do_digit(self, idx):
        # 尽力读取digit: 可能是多位数
        digit_start = idx
        while self.string[idx].isdigit():
            idx += 1
        digit_end = idx
        num = int(self.string[digit_start:digit_end])
        self.num_stack.append(num)
        self.str_stack.append(self.EMPTY_STR_SLOT)

        # assert self.string[idx] == "["
        idx += 1
        return idx


    def _do_alpha(self, idx):
        alpha_start = idx
        while idx < self.len and self.string[idx].isalpha():
            idx += 1
        alpha_end = idx
        self.str_stack[-1] += self.string[alpha_start:alpha_end]
        return idx

    def _do_close_brace(self, idx):
        # assert c == ']'
        n = self.num_stack.pop()
        s = self.str_stack.pop()
        self.str_stack[-1] += n * s
        idx += 1
        return idx


def main():
    print("start main")
    s = Solution()
    # input = 'abc3[a]'
    # input = '4[ac]dy'
    input = '3[2[ad]3[pf]]xyz'
    ret = s.expressionExpand(input)
    print(ret)

if __name__ == "__main__":
    main()
